package com.xhh.learning.record.algorithm.knapsack;

/**
 * 类名： DP1
 * 描述：
 * 公司： 北京海鑫科金高科技股份有限公司
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/5/28 16:08
 * 最后修改时间:  2019/5/28 16:08
 */
public class DP1 {

    public static void main(String[] args) {
        // int[] a = {2, 9, 3, 6, 5, 1, 7};
        int[] a = {3, 2, 5, 8, 9, 1, 7};
        int i = longestIncreaseSubArrayDP(a, a.length);
        System.out.println(i);
    }

    private static int longestIncreaseSubArrayDP(int[] a, int n) {
        int[] maxLen = new int[n];
        maxLen[0] = 1;
        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j] && maxLen[j] > max) {
                    max = maxLen[j];
                }
            }
            maxLen[i] = max + 1;
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            if (maxLen[i] > max) {
                max = maxLen[i];
            }
        }
        return max;
    }


}
